/*  
 * i-OSGi - Tunable Bundle Isolation for OSGi
 * Copyright (C) 2011  Sven Schulz
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.iosgi.impl.engine;

import java.net.URI;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.felix.ipojo.annotations.Component;
import org.apache.felix.ipojo.annotations.Provides;
import org.apache.felix.ipojo.annotations.Requires;
import org.iosgi.IsolationConstraint;
import org.iosgi.IsolationConstraintRegistry;
import org.iosgi.engine.IsolationEngine;
import org.iosgi.engine.Operation;
import org.iosgi.impl.BundleOperation;
import org.iosgi.impl.EnvironmentIDs;
import org.iosgi.impl.IsolationEnvironmentOperation;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import algorithms.graphColorer.Colorer;
import algorithms.graphColorer.reoptimizer.IteratedGreedyColorer;
import dataStructures.graph.Edge;
import dataStructures.graph.ExtendedSimpleGraphAjazenzList;
import dataStructures.graph.ExtendedUndirectedGraph;
import dataStructures.graph.GraphColoring;

/**
 * @author Sven Schulz
 */
@Component(immediate = true)
@Provides(specifications = IsolationEngine.class)
public class IsolationEngineImpl implements IsolationEngine {

	private static final Logger LOGGER = LoggerFactory
			.getLogger(IsolationEngineImpl.class);

	public enum OptimizationMode {
		NONE, ITERATED_GREEDY, PSEUDO_BOOLEAN
	}

	@Requires
	private IsolationConstraintRegistry constraintRegistry;

	private Cell root;
	private int depth;
	private OptimizationMode optimizationMode;

	public IsolationEngineImpl() {
		this(null, 2, OptimizationMode.PSEUDO_BOOLEAN);
	}

	IsolationEngineImpl(final IsolationConstraintRegistry registry, int depth,
			OptimizationMode optimizationMode) {
		this.constraintRegistry = registry;
		this.depth = depth;
		this.optimizationMode = optimizationMode;
		root = new Cell();
	}

	@Override
	public List<Operation> install(String location) throws Exception {
		List<Operation> ops = new LinkedList<Operation>();
		root.add(location, ops);
		optimize(ops);
		return ops;
	}

	@Override
	public List<Operation> uninstall(String location) throws Exception {
		List<Operation> ops = new LinkedList<Operation>();
		root.remove(location, ops);
		optimize(ops);
		return ops;
	}

	void optimize(List<Operation> ops) {
		Set<Operation> subsumed = new HashSet<Operation>();
		for (int i = 0; i < ops.size(); i++) {
			Operation op = ops.get(i);
			for (int j = 0; j < i; j++) {
				Operation c = ops.get(j);
				if (!subsumed.contains(c) && op.subsumes(c))
					subsumed.add(c);
			}
		}
		int sc = 0;
		for (Iterator<Operation> it = ops.iterator(); it.hasNext();) {
			Operation op = it.next();
			if (subsumed.contains(op)) {
				it.remove();
				sc++;
			}
		}
		if (sc > 0) {
			LOGGER.debug("{} operations subsumed", sc);
		}
	}

	@Override
	public String toString() {
		return root.toString();
	}

	int[] calc() {
		int[] counts = new int[depth + 1];
		LinkedList<Cell> open = new LinkedList<Cell>();
		open.add(root);
		while (!open.isEmpty()) {
			Cell c = open.pop();
			open.addAll(c.children);
			counts[c.getLevel()]++;
		}
		return counts;
	}

	class Cell {

		private int childSn;
		private Set<String> bundles;
		private Cell parent;
		private List<Cell> children;
		private String target;

		Cell() {
			this(null);
		}

		Cell(final Cell parent) {
			this.childSn = 0;
			this.parent = parent;
			bundles = new HashSet<String>();
			children = new LinkedList<Cell>();
			if (parent != null)
				parent.children.add(this);
			target = (parent != null ? (parent.target + "/") + parent.childSn++
					: "");
		}

		void verify() {
			for (String a : bundles) {
				for (String b : bundles) {
					int lvl = constraintRegistry.getIsolationLevel(a, b);
					if (lvl < this.getLevel()) {
						throw new RuntimeException("verification failed");
					}
				}
			}
		}

		void add(final String location, List<Operation> ops) {
			bundles.add(location);
			if (this.getLevel() < depth) {
				boolean added = false;
				for (Cell c : children) {
					if (c.isCompatible(location)) {
						c.add(location, ops);
						added = true;
						break;
					}
				}
				if (!added) {
					Cell c = new Cell(this);
					ops.add(new IsolationEnvironmentOperation(
							IsolationEnvironmentOperation.Type.CREATE, c
									.getTarget()));
					c.add(location, ops);
					if (optimizationMode != OptimizationMode.NONE)
						optimize(ops);
				}
			} else {
				ops.add(new BundleOperation(BundleOperation.Type.INSTALL, this
						.getTarget(), location));
			}
			verify();
		}

		void remove(final String location, List<Operation> ops) {
			bundles.remove(location);
			if (this.getLevel() < depth) {
				for (Iterator<Cell> it = children.iterator(); it.hasNext();) {
					Cell c = it.next();
					if (c.getBundles().contains(location)) {
						c.remove(location, ops);
						if (this.getLevel() > 0 && c.isEmpty()) {
							it.remove();
							if (EnvironmentIDs.isDestructible(URI.create(this
									.getTarget()))) {
								ops.add(new IsolationEnvironmentOperation(
										IsolationEnvironmentOperation.Type.DESTROY,
										this.getTarget()));
							}
						}
						break;
					}
				}
			} else {
				ops.add(new BundleOperation(BundleOperation.Type.UNINSTALL,
						this.getTarget(), location));
			}
		}

		public Cell getParent() {
			return parent;
		}

		public List<Cell> getChildren() {
			return children;
		}

		String getTarget() {
			return target;
		}

		int getLevel() {
			Cell p = this.getParent();
			return p != null ? p.getLevel() + 1 : 0;
		}

		boolean isCompatible(final String location) {
			for (String b : bundles) {
				int lvl = constraintRegistry.getIsolationLevel(location, b);
				if (lvl < this.getLevel()) {
					return false;
				}
			}
			return true;
		}

		Set<String> getBundles() {
			return bundles;
		}

		boolean isEmpty() {
			return this.getBundles().isEmpty();
		}

		@Override
		public String toString() {
			StringBuilder b = new StringBuilder();
			for (int i = 0; i < this.getLevel(); i++) {
				b.append('\t');
			}
			b.append("[ ");
			for (String location : bundles) {
				b.append(location).append(' ');
			}
			b.append(']');
			for (Cell c : children) {
				b.append('\n');
				b.append(c);
			}
			return b.toString();
		}

		void optimize(List<Operation> ops) {

			if (this.getLevel() == depth) {
				return;
			}

			ExtendedUndirectedGraph<String, Edge<String>> g = new ExtendedSimpleGraphAjazenzList<String>();
			for (String b : bundles) {
				g.addVertex(b);
			}
			for (String b : bundles) {
				for (IsolationConstraint c : constraintRegistry
						.getConstraints(b)) {
					if (c.getLevel() <= this.getLevel()) {
						String[] cp = c.getBundles();
						if (g.containsVertex(cp[0]) && g.containsVertex(cp[1])) {
							g.addEdge(cp[0], cp[1]);
						}
					}
				}
			}
			GraphColoring<String, Edge<String>> base = new GraphColoring<String, Edge<String>>(
					g);
			int color = 1;
			for (Cell c : this.getChildren()) {
				for (String b : c.getBundles()) {
					base.setColor(b, color);
				}
				color++;
			}

			Colorer<String, Edge<String>> colorer = null;
			switch (optimizationMode) {
			case ITERATED_GREEDY: {
				colorer = new IteratedGreedyColorer<String, Edge<String>>(g,
						1000, base);
				break;
			}
			case PSEUDO_BOOLEAN: {
				colorer = new PseudoBooleanColorer<String, Edge<String>>(g);
				break;
			}
			}

			long ref = System.currentTimeMillis();
			GraphColoring<String, Edge<String>> optimized = colorer
					.getColoring();
			long elapsed = System.currentTimeMillis() - ref;
			LOGGER.debug(
					"level: {}, new: {}, old: {}, elapsed: {} ms",
					new Object[] { this.getLevel(),
							optimized.getNumberOfColors(),
							base.getNumberOfColors(), elapsed });
			if (optimized.getNumberOfColors() == base.getNumberOfColors()) {
				return;
			}

			/* Find least cost match. */
			List<Set<String>> a = new LinkedList<Set<String>>(), b = new LinkedList<Set<String>>();
			for (Cell c : children) {
				Set<String> s = new HashSet<String>(c.getBundles());
				a.add(s);
			}
			b = new LinkedList<Set<String>>(optimized.getColorVertexMapping()
					.values());
			while (b.size() < a.size())
				b.add(new HashSet<String>());

			ref = System.currentTimeMillis();
			Map<Integer, Integer> matching = SetMatching.findBestMatch(a, b);
			LOGGER.debug("matching took {} ms", System.currentTimeMillis()
					- ref);
			for (Map.Entry<Integer, Integer> e : matching.entrySet()) {
				Integer cellIdx = e.getKey();
				Set<String> s1 = a.get(cellIdx), s2 = b.get(e.getValue());
				Cell c = children.get(cellIdx);
				boolean dirty = false;
				for (String r : s1) {
					if (!s2.contains(r)) {
						c.remove(r, ops);
						dirty = true;
					}
				}
				for (String r : s2) {
					if (!s1.contains(r)) {
						c.add(r, ops);
						dirty = true;
					}
				}
				if (dirty && !c.isEmpty()) {
					c.optimize(ops);
				}
			}
			for (Iterator<Cell> it = children.iterator(); it.hasNext();) {
				Cell c = it.next();
				if (c.isEmpty())
					it.remove();
			}
		}
	}

	interface CellVisitor {
		void visit(Cell c);
	}

}